package my.algorithms.mcorrea.topcoder;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * http://community.topcoder.com/stat?c=problem_statement&pm=1524&rd=4472
 * DFS
 * @author mcorrea
 */
public class Marketing {
	
	public static void main(String args[]){
		System.out.println(howMany(new String[]{"1 4","2","3","0",""}));
		System.out.println("***********************************************");
		System.out.println(howMany(new String[]{"1","2","0"}));
		System.out.println("***********************************************");
		System.out.println(howMany(new String[]{"", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", ""}));
		
	}
	
	public static long howMany(String[] compete){
		Map<Integer, Set<Integer>> graph = new HashMap<Integer, Set<Integer>>();
		//init graph
		for(int k=0; k<compete.length; k++){
			graph.put(k, new HashSet<Integer>());
		}
	
		//decode
		int pos = 0;
		for(String s: compete){
			String[] competes = s.split("");
			for(String c: competes){
				try{
					Integer temp = Integer.parseInt(c);
					if(temp!=-1){
						graph.get(pos).add(temp);
						graph.get(temp).add(pos);
					}
				}catch(Exception e){}
			}
			pos++;
		}
		printG(graph);
		//find optimal path for teenages and adults
		
		//start DFS traverse the Tree, if every edge is visited with
		//the condition then there is a path and should sum to the total
		String path[] = new String[compete.length]; //if there is some NULL after DFS then no Path
		boolean[] visited = new boolean[compete.length];
		Arrays.fill(visited, false); //fills all the array: necesary for DFS
		Arrays.fill(path, null);
		
		//visit all nodes
		int count = 0;
		for(int k=0; k<compete.length; k++){
			if(!visited[k]){
				if( DFSVisit(graph, visited, k, "Teenagers", path, count))
					count++;
			}
		}
		
	/*	Arrays.fill(visited, false);
		Arrays.fill(path, null);
		for(int k=0; k<compete.length; k++){
			if(!visited[k]){
				if( DFSVisit(graph, visited, k, "Adults", path, count))
					count++;
			}
		}*/
		if(count ==0)return -1;
		
		long res = 1;
		while (count-- > 0) res *= 2;
		
		System.out.println("---------------------");
		System.out.println(count);
		
		return res;
	}
	
	public static boolean DFSVisit(Map<Integer, Set<Integer>> graph, boolean[] visited,
			Integer u, String condition, String[] path, int count){
		
		visited[u] = true;
		path[u] = condition;
		condition = condition.equals("Teenagers")?"Adults": "Teenagers";
		
		for(Integer edge: graph.get(u)){
			if(!visited[edge]){
				DFSVisit(graph, visited, edge, condition, path, count+1 );
			}else{
				//detect conflict
				if(!path[edge].equals(condition)){
					return false;
				}
			}
		}
		
		return true;
	}
	
	
	
	public static void printG(Map<Integer, Set<Integer>> graph){
	System.out.println("-------------------------");
		for(Integer k: graph.keySet()){
			System.out.print(k+" --> ");
			for(Integer e: graph.get(k)){
				System.out.print(e+",  ");
			}
		}
		System.out.println("\n--------------------");
	}
	
	
}
